#include <string>
#include <vector>
#include <unordered_set>

using namespace std;


/**
 * @brief 52. N 皇后 II
 * https://leetcode.cn/problems/n-queens-ii/
 */
class Solution {
public:
    int totalNQueens(int n) {
        unordered_set<int> cols, diag1, diag2;
        return dfs(n, 0, cols, diag1, diag2);
    }

    int dfs(int& n, int row, unordered_set<int>& cols, unordered_set<int>& diag1, unordered_set<int>& diag2) {
        if (row == n) {
            return 1;
        } else {
            int res = 0;
            for (int i=0; i<n; i++) {
                if (cols.find(i) != cols.end()) continue;
                int d1 = row-i;
                if (diag1.find(d1) != diag1.end()) continue;
                int d2 = row+i;
                if (diag2.find(d2) != diag2.end()) continue;

                cols.insert(i);
                diag1.insert(d1);
                diag2.insert(d2);
                res += dfs(n, row+1, cols, diag1, diag2);
                cols.erase(i);
                diag1.erase(d1);
                diag2.erase(d2);
            }
            return res;
        }
    }
};